package com.leetcode.algorithm.y22.m09.w3;

import com.leetcode.algorithm.common.TreeNode;

/**
 * 1022. 从根到叶的二进制数之和
 * 
 * https://leetcode.cn/problems/sum-of-root-to-leaf-binary-numbers/
 * 
 * @author jie.deng
 *
 */
class Question1022Solution01 {

	public int sumRootToLeaf(TreeNode root) {
		if (root == null) {
			return 0;
		}
		int[] resultRef = new int[] { 0 };
		dfs(root, 0, resultRef);
		return resultRef[0];
	}

	// 0.确定入参和返回值
	private void dfs(TreeNode root, int num, int[] resultRef) {
		// 2.当前层逻辑
		num <<= 1;
		num += root.val;

		// 1.递归终止条件
		if (root.left == null && root.right == null) {
			resultRef[0] += num;
			return;
		}
		// 3.递归调用
		if (root.left != null) {
			dfs(root.left, num, resultRef);
		}
		if (root.right != null) {
			dfs(root.right, num, resultRef);
		}
		// 4.回溯(若有)
	}

}